/*
 * @lc app=leetcode.cn id=45 lang=typescript
 *
 * [45] 跳跃游戏 II
 */

// @lc code=start
function jump(nums: number[]): number {
  if (nums.length <= 1) return 0;

  let ans = 1;
  // 当前能跳跃的最小位置
  let pre = 1;
  // 当前最多可以跳到哪里
  let pos = nums[0];
  while (pos < nums.length - 1) {
    let k = pre;
    // 跳跃范围内再找一个最大跳跃步数
    for (let i = k + 1; i <= pos; i++) {
      if (i + nums[i] > k + nums[k]) k = i;
    }
    // 找到范围内的最大跳跃次数，完成一次跳跃
    pre = pos + 1;
    pos = k + nums[k];
    ans++;
  }

  return ans;
}
// @lc code=end
